//////////////////////////////////////////////////////////////////////////////
// Copyright (C) 2008-2010, Shane J. M. Liesegang
// All rights reserved.
// 
// Redistribution and use in source and binary forms, with or without 
// modification, are permitted provided that the following conditions are met:
// 
//     * Redistributions of source code must retain the above copyright 
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright 
//       notice, this list of conditions and the following disclaimer in the 
//       documentation and/or other materials provided with the distribution.
//     * Neither the name of the copyright holder nor the names of any 
//       contributors may be used to endorse or promote products derived from 
//       this software without specific prior written permission.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
// POSSIBILITY OF SUCH DAMAGE.
//////////////////////////////////////////////////////////////////////////////

#pragma once

#include "Common.h"
#include "BoundingShapes.h"

class SpatialGraph;
class SpatialGraphKDNode;

typedef std::vector<SpatialGraphKDNode*>		SpatialGraphNeighborList;
typedef std::vector<Vector2>					Vector2List;
typedef std::vector<bool>						BoolList;

class SpatialGraphKDNode
{
public:
	SpatialGraphKDNode(const BoundingBox& bb, SpatialGraphKDNode* _parent)
		: BBox(bb)
		, LHC(NULL)
		, RHC(NULL)
		, Parent(_parent)
	{
	}

	void Render();

	bool HasChildren() {return LHC != NULL && RHC != NULL;}
	void GetGridPoints(Vector2List& points, int& xPoints, int& yPoints);

	BoundingBox BBox;
	SpatialGraphKDNode* LHC;
	SpatialGraphKDNode* RHC;
	SpatialGraphKDNode* Parent;
	SpatialGraph*		Tree;
	int					Index;
	int					Depth;
	bool				bBlocked;

	SpatialGraphNeighborList	Neighbors;
	BoolList					NeighborLOS;
};

#if defined (__APPLE__) || defined(__linux__)
	//have to give a hashing function for specific pointers
	namespace hashmap_ns {
		template<> struct hash<SpatialGraphKDNode*>
		{
			size_t operator() (const SpatialGraphKDNode* const & x) const
			{
				return hash<long int>() ((long int)x);
			}
		};
	}

#endif

class SpatialGraph
{
public:
	SpatialGraph(float entityWidth, const BoundingBox& startBox);
	~SpatialGraph();

	SpatialGraphKDNode* FindNode(SpatialGraphKDNode* node, const BoundingBox& bbox);
	SpatialGraphKDNode* FindNode(SpatialGraphKDNode* node, const Vector2& point);
    SpatialGraphKDNode* FindNode(const BoundingBox& bbox);
    SpatialGraphKDNode* FindNode(const Vector2& point);
    void Render();

    int GetDepth() {return _depth;}
    Vector2 GetSmallestDimensions() {return _smallestDimensions;}
    bool CanGo( const Vector2& vFrom, const Vector2 vTo );

private:
    SpatialGraphKDNode* CreateTree(int depth, const BoundingBox& bbox, SpatialGraphKDNode* parent = NULL, int index = 0 );
    void AddNeighbor( SpatialGraphKDNode* node, const Vector2& pos );
    void ComputeNeighbors( SpatialGraphKDNode* node );
    void ValidateNeighbors( SpatialGraphKDNode* node );
    void DeleteNode( SpatialGraphKDNode* pNode );
    bool IsFullyBlocked( SpatialGraphKDNode* pNode );
    bool CanGoInternal( const Vector2& vFrom, const Vector2 vTo, SpatialGraphKDNode* pSourceNode, SpatialGraphKDNode* pDestNode );
    bool CanGoNodeToNode( SpatialGraphKDNode* pSourceNode, SpatialGraphKDNode* pDestNode );

private:
    int _depth;
    float _entityWidth;
    Vector2 _smallestDimensions;
    SpatialGraphKDNode* _root;
    int _dirMasks[4];

};

#define theSpatialGraph SpatialGraphManager::GetInstance()

class SpatialGraphManager
{
public:
    static SpatialGraphManager &GetInstance();

    SpatialGraph* GetGraph() {return _spatialGraph;}
    void CreateGraph( float entityWidth, const BoundingBox& bounds );

    void Render();

    bool GetPath( const Vector2& source, const Vector2& dest, Vector2List& path );

    bool CanGo( const Vector2& from, const Vector2 to );
    bool IsInPathableSpace( const Vector2& point );
    bool FindNearestNonBlocked( const Vector2& fromPoint, Vector2& goTo );
        
    void EnableDrawBounds(bool enable);
    const bool ToggleDrawBounds();
    const bool GetDrawBounds();
    void EnableDrawBlocked(bool enable);
    const bool ToggleDrawBlocked();
    const bool GetDrawBlocked();
    void EnableDrawGridPoints(bool enable);
    const bool ToggleDrawGridPoints();
    const bool GetDrawGridPoints();
    void EnableDrawGraph(bool enable);       
    const bool ToggleDrawGraph();
    const bool GetDrawGraph();
    void EnableDrawNodeIndex(bool enable);
    const bool ToggleDrawNodeIndex();
    const bool GetDrawNodeIndex();
        
protected:
    SpatialGraphManager();
    ~SpatialGraphManager();
    void Initialize();
    static SpatialGraphManager *s_SpatialGraphManager;

private:
    SpatialGraph*              _spatialGraph;
        
    bool _drawBounds;
    bool _drawBlocked;
    bool _drawGridPoints;
    bool _drawGraph;
    bool _drawNodeIndex;
};